package study;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class FindCheapestPrice {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        int mat[][] = new int[n][n];
        for (int flight[] : flights) {
            mat[flight[0]][flight[1]] = flight[2];
        }

        PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(e -> e[1]));

        int costs[] = new int[n];
        int stops[] = new int[n];
        Arrays.fill(costs, Integer.MAX_VALUE);

        minHeap.offer(new int[]{src, 0, k});
        while (!minHeap.isEmpty()) {
            int elem[] = minHeap.poll();
            int vertex = elem[0], cost = elem[1], stop = elem[2];

            if (vertex == dst) {
                return cost;
            } else if (stop < 0) {
                continue;
            }

            for (int i = 0; i < n; ++i) {
                if (mat[vertex][i] > 0) {
                    int costI = costs[i], costVI = mat[vertex][i];
                    if (cost + costVI < costI) {
                        minHeap.offer(new int[]{i, costVI + cost, stop - 1});
                        costs[i] = costVI + cost;
                        stops[i] = stop - 1;
                    } else if (stops[i] < stop - 1) {
                        minHeap.offer(new int[]{i, costVI + cost, stop - 1});
                    }
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        FindCheapestPrice cheapestPrice = new FindCheapestPrice();
        int[][] input = {{0,1, 100}, {1,2, 100}, {0,2,500}};
        int ret = cheapestPrice.findCheapestPrice(3,input, 0,2,1);
        System.out.println(ret);
    }
}
